
#ifndef __IPER_CLASS
#define __IPER_CLASS


#include "compatib.h"
//
#include "diagnost.h"




//#define _DEFAULT_DATA_CHUNK 4L

typedef unsigned int t_index;
typedef double t_real;
typedef int t_signed;

// list type
// if no buffering requested call Set_Data_Chunk(0)
// or call constructor(0);

//************************************************************************
//                                                                      **
//                      class ImpBaseList                               **
//                                                                      **
//************************************************************************



template <class T>
class ImpBaseList
	{

	//memory allocated may be zero even if dim>0 in this case
	//lis!= NULL and object is not empty even if it is not allocated
	t_index available_mem;
	//memory increment
	t_index data_chunk;

	//this prevent from calling it explicitely

	public:
	//dimension of vector
	t_index dim;
	T  * lis; //_HUGEPTR_
	//void * lis;

	

	ImpBaseList();

//	ImpBaseList(const ImpBaseList<T> & obj);

	ImpBaseList(t_index requested_data_chunk);
	void Set_Data_Chunk(t_index requested_data_chunk);
	//destroy vector and deallocate mem
	~ImpBaseList();
	//destroy vector but does not deallocate mem
	void Reset();
	//the previous functions are equivalents from user point of view


//append one element
	void Append(const T & obj);
//append a list
	void Append(const ImpBaseList<T> & obj);

//duplicate
	void operator=(const ImpBaseList<T> & source);

	T & operator [] ( t_index index );
	const T & operator [] ( t_index index ) const;

#ifdef _OPERATOR_SQUARE_BRACKET_TO_BE_DECLARED_ALSO_FOR_INT	

	T & operator [] ( int index );
	const T & operator [] ( int index ) const;
#endif

	t_index Dim() const;

protected:
	void Destroy_And_ReDim(t_index dimension);
	void Save_And_ReDim(t_index dimension);
private:
	void Disallocate_Mem();
	#ifdef __CHECK_MEMORY_ALLOC
	void Check_Mem(int check_type);
	#endif
	};

//************************************************************************
//                                                                      **
//                      class ImpSimpleTypeList                         **
//                                                                      **
//************************************************************************


//tipo lista
template <class T>
class ImpSimpleTypeList:public ImpBaseList<T>
	{
	public:
#ifdef __32BIT_CODE__
	//duplicate not sure for 16 bit platforms
	void operator=(const ImpSimpleTypeList<T> & source);
#endif
	int operator==(const ImpSimpleTypeList<T> & sub) const;
	int operator!=(const ImpSimpleTypeList<T> & sub) const;

	//Set all the number to num
	void Set(T num);

	void Destroy_And_ReDim(t_index dimension);
	void Save_And_ReDim(t_index dimension);

	};

//************************************************************************
//                                                                      **
//                      class ImpObjectList                             **
//                                                                      **
//************************************************************************


//List implementation of a generic object
template <class T>
class ImpObjectList:public ImpBaseList<T>
	{
	public:

	//destroy vector and deallocate mem
	~ImpObjectList();

	//destroy vector but does not deallocate mem
	void Reset();

	//the previous functions are equivalents from user point of view

	//append one element
	void Append(const T & obj);
	//append a list
	void Append(const ImpObjectList<T> & obj);

	//duplicate
	void operator=(const ImpObjectList<T> & source);


	void Destroy_And_ReDim(t_index dimension);
	void Save_And_ReDim(t_index dimension);

	private:
	void Init_List_ElemS(t_index start);
	};

//class for implementation of a ordered list
template <class T, class E>
class OrderedList 
	{
     
    class OrderedListElem
		{
	    
        public:

			T key;
			E info;
		           
		};
   
	public:

		ImpSimpleTypeList<t_index> tbl_index;

		t_index Dim();

		ImpObjectList<OrderedListElem> list; 

		void Get_Key (const t_index position, T & key_elem);
	 
		//return the index of key if this is already present in the ordered list
		t_index Binary_Search (const T & search_key, int & found)const;

		int Insertion(const T & new_key, const E & new_info, t_index & position);

	    E& operator[] (t_index index)
			{
			return list[tbl_index[index]].info;
			}	

		const E& operator[] (t_index index)const
			{
			return list[tbl_index[index]].info;
			}

	};

//template code file
//#include "baseclas.hpp"
int Test_Base_Class(t_index max_num=200000UL);

#include <algorithm>
/*
#ifdef  _MSC_VER
#include<memory.h>

#else
#include<mem.h>
#endif
*/

#include<string.h>

#define ITERATE_ALL(operation) 			\
		t_index _limit =Dim(); 	  		\
		for(t_index i=0;i<_limit;i++)	\
			{         					\
			operation ;					\
			}


//************************************************************************
//                                                                      **
//                      class ImpBaseList                               **
//                                                                      **
//************************************************************************

#ifdef __CHECK_MEMORY_ALLOC

template <class T>
void ImpBaseList<T>::Check_Mem(int check_type)
{
	int res;
	Check(farheapfillfree(1) < 0, "Heap corrupted");

	res = farheapcheckfree(1);
	if (res < 0)
	{
		Check((res != _HEAPCORRUPT), "Heap corrupted.");
		Check((res != _BADVALUE), "Bad value in free space.");
		Check(!(res != _BADVALUE && res != _HEAPCORRUPT), "Unknown error");
	}
	Check(!(available_mem == 0 && dim == 0 && lis == 0));


	if (farheapchecknode(lis) == tipo)
		return;
	Assert(farheapchecknode(lis) != _USEDENTRY);
	Assert(farheapchecknode(lis) != _HEAPEMPTY);
	Assert(farheapchecknode(lis) != _HEAPCORRUPT);
	Assert(farheapchecknode(lis) != _BADNODE);
	Assert(farheapchecknode(lis) != _FREEENTRY);
	merr << "unknown return code";


	return;
}
#endif


//dummy new operator used to get rid of compiler
//this operator inizializes the class doing nothing on memory allocation
//N:B: as it uses size_t  only size < 64k of classes can be inizialized
enum t_dummy_enum { dummy_flag };

#ifdef __32BIT_CODE__
/*
//this is not accepted by some compilers

inline void *operator new[](size_t size,void* where,enum t_dummy_enum temp)
	{
	return  where;
	}
*/
inline void *operator new(size_t size, void* where, enum t_dummy_enum temp)
{
	return  where;
}

#else

inline void *operator new(size_t size, void huge * where, enum t_dummy_enum temp)
{
	return  where;
}
#endif

//type list

template <class T>
inline ImpBaseList<T>::ImpBaseList() :
	dim(0UL),
	lis(NULL),
	available_mem(0UL),
	//default data_chunk is 4
	data_chunk(_DEFAULT_DATA_CHUNK) {};
/*
	//not defining copy contructor prevents from
	//calling it
	template <class T>
	ImpBaseList<T>::ImpBaseList(const ImpBaseList<T> & obj)
		{
		//merr<<"the copy constructir of this class must never be called "<<obj.Dim();
		return;
		}
*/

template <class T>
ImpBaseList<T>::ImpBaseList(t_index requested_data_chunk) :
	dim(0),
	lis(0),
	available_mem(0),
	data_chunk(requested_data_chunk) {};

template <class T>
void ImpBaseList<T>::Set_Data_Chunk(t_index requested_data_chunk)
{
	data_chunk = requested_data_chunk;
	return;
}


template <class T>
void ImpBaseList<T>::Disallocate_Mem()
{
#ifdef __CHECK_MEMORY_ALLOC
	Check_Mem(_USEDENTRY);
#endif

	if (available_mem > 0)
	{
		Assert(dim <= available_mem);
#ifdef __32BIT_CODE__
		free(lis);
#else
		farfree(lis);
#endif

		available_mem = 0UL;
		dim = 0UL;
		lis = (T _HUGEPTR_ *) 0;
	}
#ifdef __CHECK_MEMORY_ALLOC
	Check_Mem(_FREEENTRY);
#endif
	return;
}

template <class T>
inline ImpBaseList<T>::~ImpBaseList()
{
	Disallocate_Mem();
	return;
}


template <class T>
inline void ImpBaseList<T>::Destroy_And_ReDim(t_index dimension)
{
	//the last lines are elimiminated because requesting
	//a zero size memory is not an error
	//  if(dimension==0)
	//  	errmsg("ERROR: zero size dimension requested");

	if (dimension <= available_mem)
	{
		dim = dimension;
		return;
	}
	else {
		Disallocate_Mem();

#ifdef __32BIT_CODE__
		lis = (T*)malloc((dimension + data_chunk) * sizeof(T));

		if (lis == (T*)(NULL))
			merr << "not enough allocable mem: num_elem " << (dimension + data_chunk) << " size " << sizeof(T) << " tot. mem. :" << (dimension + data_chunk)*(unsigned long)sizeof(T);

#else
		lis = (T huge *) farmalloc((dimension + data_chunk) * sizeof(T));

		if (lis == (T huge *)(NULL))
			merr << "not enough allocable mem: num_elem " << (dimension + data_chunk) << " size " << sizeof(T) << " tot. mem. :" << (dimension + data_chunk)*(unsigned long)sizeof(T);

#endif

#ifdef __CHECK_MEMORY_ALLOC
		Check_Mem(_USEDENTRY);
#endif
		dim = dimension;
		available_mem = (dimension + data_chunk);
	}
	return;
}

template<class T>
inline void ImpBaseList<T>::Reset()
{
	dim = 0;
	if (available_mem == 0)
		lis = NULL;
	return;
}

template<class T>
void ImpBaseList<T>::Save_And_ReDim(t_index dimension)
{
	Check(dimension > 0, "zero size dimension requested");

	//no memory allocated
	if (available_mem == 0)
	{
		//non empty object but no memory allocated
		if (dim != 0)
		{
			T _HUGEPTR_ * temp;
			t_index i, act_dim;
			Assert(lis != NULL);
			temp = lis;
			act_dim = std::min(dim, dimension);
			Destroy_And_ReDim(dimension);
			//copy the old elements
			for (i = 0; i < act_dim; i++)
				//lis[i]=(T)temp[i];does not work on MSV4.0 
				this->lis[i] = temp[i];
		}
		//empty object
		else {
			Destroy_And_ReDim(dimension);
		}
		return;
	}

	//memory allocated
	if (dimension > available_mem)
	{
#ifdef __32BIT_CODE__
		lis = (T*)realloc(lis, (dimension + data_chunk) * sizeof(T));
		if (lis == (T*)(NULL))
			merr << "not enough Reallocable mem:: num_elem " << (dimension + data_chunk) << " size " << sizeof(T) << " tot. mem. :" << (dimension + data_chunk)*(unsigned long)sizeof(T);

#else
		lis = (T huge *) farrealloc(lis, (dimension + data_chunk) * sizeof(T));
		if (lis == (T huge *)(NULL))
			merr << "not enough Reallocable mem: num_elem " << (dimension + data_chunk) << " size " << sizeof(T) << " tot. mem. :" << (dimension + data_chunk)*(unsigned long)sizeof(T);

#endif

#ifdef __CHECK_MEMORY_ALLOC
		Check_Mem(_USEDENTRY);
#endif
		available_mem = (dimension + data_chunk);
	}
	dim = dimension;
	return;
}

template <class T>
void ImpBaseList<T>::operator= (const ImpBaseList<T> & source)
{
	t_index len;
	len = source.Dim();

	if (len > 0)
		Destroy_And_ReDim(len);
	else Reset();
	ITERATE_ALL(this->lis[i] = source[i])

		return;
}

#ifdef _OPERATOR_SQUARE_BRACKET_TO_BE_DECLARED_ALSO_FOR_INT	

template <class T>
inline T& ImpBaseList<T>::operator [] (int index)
{
	Check(index < (int)dim && index >= 0, "index = "
		<< index << ", dim = " << dim << " mem = " << available_mem);
	return (T&)this->lis[index];
}

template <class T>
inline const T& ImpBaseList<T>::operator [] (int index) const
{
	Check(index < (int)dim && index >= 0, "index = "
		<< index << ", dim = " << dim << " mem = " << available_mem);
	return (T&)this->lis[index];
};


#endif

template <class T>
inline T& ImpBaseList<T>::operator [] (t_index index)
{
	Check(index < dim, "index = "
		<< index << ", dim = " << dim << " mem = " << available_mem);

	return (T&)this->lis[index];
}

template <class T>
inline const T& ImpBaseList<T>::operator [] (t_index index) const
{
	Check(index < dim, "index = "
		<< index << ", dim =" << dim << " mem" << available_mem);

	return (T&)this->lis[index];
};
template <class T>
inline t_index ImpBaseList<T>::Dim() const
{
	return dim;
}

//append one element
template <class T>
void ImpBaseList<T>::Append(const T & obj)
{
	Save_And_ReDim(dim + 1);
	(*this)[dim - 1] = obj;
	return;
}

//append a list
template <class T>
void ImpBaseList<T>::Append(const ImpBaseList<T> & obj)
{
	t_index old_dim, i;
	old_dim = dim;
	Save_And_ReDim(old_dim + obj.Dim());
	for (i = old_dim; i < dim; i++)
		(*this)[i] = obj[i - old_dim];
	return;
}


//************************************************************************
//                                                                      **
//                      List implementation of Simple Type              **
//                                                                      **
//************************************************************************

#ifdef __32BIT_CODE__
template <class T>
void ImpSimpleTypeList<T>::operator=(const ImpSimpleTypeList<T> & source)
{
	t_index lim = source.Dim();
	Destroy_And_ReDim(lim);
	memcpy((void *)this->lis, (void *)source.lis,
		lim*((char *)&(source.lis[1]) - (char *)source.lis));

	return;
}
#endif


template <class T>
void ImpSimpleTypeList<T>::Set(T num)
{
	ITERATE_ALL(this->lis[i] = (T)(num))

		return;
}

template <class T>
void ImpSimpleTypeList<T>::Destroy_And_ReDim(t_index dimension)
{
	ImpBaseList<T>::Destroy_And_ReDim(dimension);
	ITERATE_ALL(this->lis[i] = (T)(0))
		return;
}

template<class T>
void ImpSimpleTypeList<T>::Save_And_ReDim(t_index dimension)
{
	t_index i = Dim(), lim;

	ImpBaseList<T>::Save_And_ReDim(dimension);
	//equivalent of Init_List_ElemS
	lim = Dim();
	for (; i < lim; i++)
		this->lis[i] = (T)(0);

	return;
}

template <class T>
int ImpSimpleTypeList<T>::operator== (const ImpSimpleTypeList<T> &string1) const
{
	t_index i = 0UL, lim = Dim();
	if (lim != string1.Dim())
		return false;
	else {

		while (i < lim && this->lis[i] == string1[i])
			i++;
		if (i == lim)
			return true;
		else return false;
	}
}

template<class T>
int ImpSimpleTypeList<T>::operator != (const ImpSimpleTypeList<T> &string1) const
{
	t_index i = 0UL, lim = Dim();

	if (lim != string1.Dim())
		return true;
	else {

		while (i < lim && this->lis[i] == string1[i])
			i++;
		if (i == lim)
			return false;
		else return true;
	}
}

//************************************************************************
//                                                                                                                                              **
//                      List implementation of objects                                                          **
//                                                                                                                                              **
//************************************************************************

template <class T>
ImpObjectList<T>::~ImpObjectList()
{
	ITERATE_ALL(this->lis[i].T::~T());
	return;
}
template <class T>
void ImpObjectList<T>::Reset()
{
	ITERATE_ALL(this->lis[i].T::~T());

	ImpBaseList<T>::Reset();

	return;
}


template <class T>
inline void ImpObjectList<T>::Destroy_And_ReDim(t_index dimension)
{
	//this-> added for GNU
	this->ImpObjectList<T>::~ImpObjectList();
	ImpBaseList<T>::Destroy_And_ReDim(dimension);
	Init_List_ElemS(0);
	return;
}

template<class T>
void ImpObjectList<T>::Save_And_ReDim(t_index dimension)
{
	t_index lastdim = Dim();
	ImpBaseList<T>::Save_And_ReDim(dimension);
	Init_List_ElemS(lastdim);
	return;
}

//this routine may be changed for 32 bit platforms
//to do inizialization in one shot using the array new
//and speed up inizialization

template <class T>
void ImpObjectList<T>::Init_List_ElemS(t_index start)
{
	t_index num, i;
	enum t_dummy_enum temp = dummy_flag;

	if (start >= Dim())
		return;
	num = Dim() - start;

#ifdef __32BIT_CODE__
	void* pdummy;

	T* pdummy2;
	Check(lis != (T*)0, "Null pointer passed");
	pdummy = (void  *) &(this->lis[start]);
	//		pdummy2= new (pdummy,temp) T[num];

#else
	void huge * pdummy;
	T huge * pdummy2;

	Check(lis != (T huge *)0, "Null pointer passed");
	pdummy = (void  huge *) &(this->lis[start]);
#endif




	//new handles only unsigned int
	//pdummy2= new (pdummy) T[n>1] doesn't work
	//on Borland c++3.1 even if it should work
	//as far as I know this is the only method to invoke
	//standard constructorsof objects
	for (i = 0; i < num; i++)
	{
		//new is a dummy routine that forces compiler
		//to initialize objects

		pdummy2 = new (pdummy, temp) T;

		Check(pdummy2 == pdummy, "ERROR: Compiler doesn't work properly");

		pdummy2++;
		pdummy = pdummy2;
	}


	return;
}

template <class T>
void ImpObjectList<T>::operator= (const ImpObjectList<T> & source)
{
	t_index len;
	len = source.Dim();
	if (len > 0)
		Destroy_And_ReDim(len);
	else Reset();
	ITERATE_ALL((*this)[i] = source[i]);

	return;
}
//append one element
template <class T>
void ImpObjectList<T>::Append(const T & obj)
{
	Save_And_ReDim(Dim() + 1);
	(*this)[Dim() - 1].T::operator=(obj);
	return;
}

//append a list
template <class T>
void ImpObjectList<T>::Append(const ImpObjectList<T> & obj)
{
	t_index old_dim, i, dim_new;

	old_dim = Dim();
	Save_And_ReDim(old_dim + obj.Dim());
	dim_new = Dim();
	for (i = old_dim; i < dim_new; i++)
		(*this)[i] = obj[i - old_dim];

	return;
}

//************************************************************************************//
//                                                                                    //
//                         class OrderedList                                          //
//                                                                                    //
//************************************************************************************//

template <class T, class E>
void OrderedList<T, E>::Get_Key(const t_index position, T & key_elem)
{
	key_elem = list[tbl_index[position]].key;
	return;
}


//Binary_Search gives back the index (position in the ordered list)
//of the word if the word is present (found ==true),
//else returns the index where must be inserted the new word (found==false).
template <class T, class E>
t_index OrderedList<T, E>::Binary_Search(const T &search_key, int & found)const
{
	found = false;
	t_signed inf = 0;
	t_signed sup = list.Dim() - 1;
	t_signed mid;

	while (inf <= sup)
	{
		mid = (inf + sup) / 2;
		if (search_key < list[tbl_index[mid]].key)
			sup = mid - 1;
		else if (search_key > list[tbl_index[mid]].key)
			inf = mid + 1;
		else {
			found = (int)true;
			return mid;
		}
	}

	return (t_index)inf;
} //end of Binary_Search function

//return true if the key is already present in the ordered list
//in position return the position in the ordered list of the new_key (also if already present)
template <class T, class E>
int OrderedList<T, E>::Insertion(const T & new_key, const E & new_info, t_index & position)

{
	t_index i;
	t_index dim = list.Dim() + 1;
	int present;

	position = Binary_Search(new_key, present);

	if (!present)
	{
		OrderedListElem new_elem;
		new_elem.key = new_key;
		new_elem.info = new_info;

		list.Append(new_elem);

		tbl_index.Save_And_ReDim(dim);

		Assert(position <= dim - 1);

		if (position < dim - 1)
		{
			for (i = dim - 1; i > position; i--)
				tbl_index[i] = tbl_index[i - 1];
			tbl_index[position] = dim - 1;
		}
		else tbl_index[position] = position;
	}
	return present;

}//end of Insertion function


template <class T, class E>
t_index OrderedList<T, E>::Dim()
{
	return list.Dim();
}



#endif

